Corelab Seminar
2018-2019
Eleni Bakali
On properties of counting functions with easy decision version: completeness, approximability, Markov chains and phase transitions for TotP-complete problems
Abstract.
We consider functions that count the number of solutions to NP decision problems. The number of solutions from NP-complete problems is hard to compute, but there are hard counting problems with the corresponding decision problem in P. TotP is a subclass of #P that contains all self-reducible problems with easy decision version.
First, we will present the first completeness results for TotP, under parsimonious reductions, which are the strictest type of reductions.
Secondly, we present approximability results for TotP: We show how problems can be approximated on instances with too many or very few solutions. We find a family of instances that we prove it includes non-approximable in polynomial-time instances (unless NP = RP). We show that every problem in TotP admits better exponential time approximations than the hard problems in #P. We study the relation between TotP and FPRAS in relation to P vs RP and RP vs NP, showing on the one hand that TotP is a subset of FPRAS if and only if NP = RP, on the other hand FPRAS is not a subset of TotP unless RP = P.
At last, we consider weighted versions of TotP-complete problems. We study the complexity of computing these weighted sums and show the existence of phase transition from NP-hard to approximate to approximable with FPRAS. We also study Markov chains for these problems and show the existence of phase transitions from exponential to polynomial mixing time.